This invention relates generally to digital circuitry for performing a rounding operation on a binary number. Rounding is often required in conjunction with an arithmetic operation, such as multiplication. For example, if an arithmetic operation is performed to a high degree of accuracy, perhaps producing a product of thirty-two binary digits or bits, it may be required to express this result in a form that is rounded to some lesser number of bits of accuracy.
Rounding may be performed by adding a "1" bit at a bit position one less in significance than the least significant bit position of the desired result. For example, if it was desired to obtain a seventeen-bit rounded binary product using bits 14-30 of an unrounded number, a "1" would be added at the thirteenth bit position. If there was an "0" at this position of the product, rounding would have no effect at all. However, if there was a "1" at bit position thirteen, this would cause a rounding bit to be carried into bit position fourteen. If there was also a "1" in this position, another carry would be generated, into bit position fifteen. So long as a "1" is present in a bit position of the unrounded number, and in all bit positions of lesser significance, the rounding operation will generate a carry into the next most significant bit position. When a "0" bit is encountered in the unrounded number, the rounding carry will produce a "1" at that position, and no further carry into the next bit position.
Rounding by this process requires the rounding carry, if any, to "ripple" across the number being rounded until the first zero is encountered. Although the process is simple, it requires much circuitry and a large number of gate delay times to execute, since the ripple process is a serial one. For high-speed operation, some form of look-ahead rounding process is more desirable, so that the separate bits of the rounded number can be computed in parallel rather than one after the other. In some types of circuitry, the rounding operation may be integrated with an associated arithmetic step, such as addition. However, in other types of circuitry, it may not be possible to perform rounding other than as a separate step following some other operation. In the latter case, parallel rounding can be performed by circuitry that includes a number of AND gates with multiple inputs. The result at any particular bit position is computed by first taking the logical AND of all the bits of lesser significance, including the rounding carry bit into the least significant bit position. If the result of the ANDing operation is a "1", then a "1" is added to the binary quantity at the current bit position, which will result in a complementing of the bit at that position. If the result of the ANDing operation is a "0", the current bit position will be unaffected by rounding.
Although this technique has the requisite parallelism and speed, it is very costly in terms of circuit complexity, and the area that the circuitry occupies on an integrated-circuit chip. Constructing AND gates with large numbers of inputs using conventional circuitry uses up a great deal of circuit chip "real estate" and renders the circuit much more costly.
It will be appreciated from the foregoing that there is still need for improvement in the field of rounding circuitry used in many arithmetic operations in integrated circuitry. In particular, the ideal rounding circuit should operate in a parallel or look-ahead fashion, but should not result in highly complex and costly circuitry. The present invention satisfies this need.